CODE 1. Palindrome Partitioning II

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/08/2013-09-08-CODE 1 Palindrome Partitioning II/

访问原文「CODE 1. Palindrome Partitioning II」

Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning ofs.
For example, givens="aab",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.

/**
 * 使用动态规划计算任意两点间是否为回文
 * @param s 字符串
 * @return  最小Cut次数
 */
private int partition(String s) {
	if (s == null || s.length() == 0)
		return 0;
	
	boolean[][] isPalindromes = new boolean[s.length()][s.length()]; // 表示任意两点之间的字符串是否为回文

	for (int i = 0; i < s.length(); i++) {
		isPalindromes[i][i] = true;
	}
	for (int i = s.length() - 2; i >= 0; i--) {
		isPalindromes[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
		for (int j = i + 2; j < s.length(); j++)
			isPalindromes[i][j] = (s.charAt(i) == s.charAt(j)) && isPalindromes[i + 1][j - 1];
	}

	return getMinCut(s, isPalindromes);
}

/**
 * 使用动态规划计算最小Cut次数
 * @param s 字符串
 * @param isPalindromes 表示任意两点之间的字符串是否为回文
 * @return
 */
private int getMinCut(String s, boolean[][] isPalindromes) {
	int[] cuts = new int[s.length()];
	for (int i = s.length() - 1; i >= 0; i--) {
		if (isPalindromes[i][s.length() - 1]) {
			cuts[i] = 0;
			continue;
		}
		int min = Integer.MAX_VALUE;
		for (int j = s.length() - 2; j >= i; j--) {
			if (isPalindromes[i][j]) {
				int tmp = 1 + cuts[j + 1];
				min = min > tmp ? tmp : min;
			}
		}
		cuts[i] = min;
	}
	return cuts[0];
}